package com.wxg.algorithm.chapter03.comparable;

import com.wxg.algorithm.chapter02.comparable.InsertionSortV2;
import com.wxg.algorithm.chapter02.util.SortTestHelper;
import com.wxg.algorithm.common.ISort;

import java.util.Random;

public class QuickSortV5ThreeWays<T extends Comparable> implements ISort<T> {

    public static final Random RAND = new Random();

    private InsertionSortV2 insertionSortV2;

    public QuickSortV5ThreeWays(){
        insertionSortV2 = new InsertionSortV2<T>();
    }

    @Override
    public void sort(T[] arr) {
        quickSort(arr, 0, arr.length-1);
    }

    /**
     * 对 arr[l...r]部分进行快速排序
     *
     * @param arr
     * @param l
     * @param r
     */
    private void quickSort(T[] arr, int l, int r) {
        // 优化, 当元素数量较少时,切换为使用"插入排序"
        if(r - l <= 15){
            insertionSortV2.sort(arr, l, r);
            return;
        }

        // partition
        int _targetIndex = RAND.nextInt(r-l+1) + l;

        swap(arr, l, _targetIndex);

        T v = arr[l];

        int lt = l; // arr[l+1...lt] < v
        int gt = r + 1; // arr[gt...r] > v
        int i  = l + 1; // arr[lt+1...i) == v
        while (i < gt) {
            if ( arr[i].compareTo(v) < 0 ) {
                swap( arr, i, lt+1 );
                lt ++;
                i ++;
            }else if ( arr[i].compareTo(v) > 0 ){
                swap( arr, i, gt-1 );
                gt --;
                // i ++; // i 索引不需要改变,此时它的指向是下一个待处理的元素
            }else { // arr[i].compareTo(v) == 0
                i ++;
            }
        }
        swap(arr, l, lt);

        quickSort(arr, l, lt-1);
        quickSort(arr, gt, r);
    }

    private void swap(T[] arr, int a, int b){
        T temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void main(String[] args) {
        QuickSortV5ThreeWays<Integer> qs = new QuickSortV5ThreeWays<>();
        MergeSortV2<Integer> ms = new MergeSortV2<>();

        int n = 100000; // 这里不能设置过大, 否则会出现内存溢出的情况。
        Integer[] intArr = SortTestHelper.generateRandomArray(n, 0, n);
        Integer[] intArr02 = SortTestHelper.copyIntArray(intArr);

        SortTestHelper.testSort(qs, intArr);
        SortTestHelper.testSort(ms, intArr02);

        System.out.println("=== 分隔线 ===");
        System.out.println("当优化后(随机选择一个元素), 对 - 近乎有序的数组的排序 - 快速排序 - 表现很优秀了");

        Integer[] intArr03 = SortTestHelper.generateNearlyOrderedArray(n, 100);
        Integer[] intArr04 = SortTestHelper.copyIntArray(intArr03);

        SortTestHelper.testSort(qs, intArr03);
        SortTestHelper.testSort(ms, intArr04);

        System.out.println("=== 分隔线 ===");
        System.out.println("对包含大量重复元素的数组排序");

        Integer[] intArr05 = SortTestHelper.generateRandomArray(n, 0, 10);
        Integer[] intArr06 = SortTestHelper.copyIntArray(intArr05);

        SortTestHelper.testSort(qs, intArr05);
        SortTestHelper.testSort(ms, intArr06);
    }
}
